package org.ala.linshen.dp;

/**
 * 给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
 *
 * 环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。
 *
 * 子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,-2,3,-2]
 * 输出：3
 * 解释：从子数组 [3] 得到最大和 3
 * 示例 2：
 *
 * 输入：nums = [5,-3,5]
 * 输出：10
 * 解释：从子数组 [5,5] 得到最大和 5 + 5 = 10
 * 示例 3：
 *
 * 输入：nums = [3,-2,2,-3]
 * 输出：3
 * 解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
 *
 *
 * 提示：
 *
 * n == nums.length
 * 1 <= n <= 3 * 104
 * -3 * 104 <= nums[i] <= 3 * 104​​​​​​​
 *
 * @author ala
 * @date 2024-09-18 12:34
 */
public class Q918 {

    public static void main(String[] args) {
        Q918 q = new Q918();

//        int[] nums = {1,-2,3,-2};
//        int[] nums = {5, -3, 5};
//        int[] nums = {3, -2, 2, -3};
//        int[] nums = {-1,3,-3,9,-6,8,-5,-5,-6,10};
        int[] nums = {-10, -7, 9, -7, 6, 9, -9, -4, -8, -5};

        System.out.println(q.maxSubarraySumCircular(nums));
    }

    public int maxSubarraySumCircular(int[] nums) {
        return V1(nums);
    }
    /**
     *  1）分别找到 最大子数组maxS 和 最小子数组minS
     *  2）如果最大子数组就是数组中间，那直接返回 maxS
     *  3）如果最大子数组被负数截成两段，那中间元素尽可能小，才能保证 maxS 尽可能大
     *  4）取 max(maxS, sum - minS)
     *  5）如果minS == sum，说明最小子数组就是整个数组，那取数组中最大值作为单个元素的maxS
     */
    protected int V1(int[] nums) {
        int N = nums.length;

        //  取 maxS 和 minS
        int maxS = nums[0], mxp = maxS, minS = nums[0], mnp = minS;
        int sum = nums[0], max = nums[0];
        for (int i = 1 ; i < N ; i++) {
            int vmx = Math.max(mxp + nums[i], nums[i]),
                vmn = Math.min(mnp + nums[i], nums[i]);
            maxS = Math.max(maxS, vmx);
            mxp = vmx;
            minS = Math.min(minS, vmn);
            mnp = vmn;

            sum += nums[i];
            max = Math.max(max, nums[i]);
        }

        //  如果 sum == minS，说明最小子数组就是整个数组
        if (sum == minS) {return maxS;}
        //  否则返回 max(maxS, sum - minS)
        else {
            return Math.max(maxS, sum - minS);
        }
    }
}
